package com.demo.datastructure.heap;

/**
 * @description: 力扣703： 数据流中的第k大元素
 * @author: ljr
 * @create: 2022/1/21 10:56 AM
 */
public class KthLargest {

    private int k;

    private Heap heap;

    public KthLargest(int k, int[] nums) {
        if(k == 0){ throw new RuntimeException(""); }
        k = k;
        heap = new Heap(k);
        if(nums != null){
            for(int i = 0; i < nums.length; i++){
                heap.insert(nums[i]);
            }
        }
    }

    public int add(int val) {
        heap.insert(val);
        return heap.getNum();
    }

    //维护一个小顶堆
    public static class Heap{

        private int n = 0;
        private Integer[] nums;

        public Heap(int length){
            nums = new Integer[length];
        }

        public void insert(int num){
            if(n == 0){
                nums[n++] = num;
                return;
            }

            if(n == nums.length){
                if(nums[0] >= num){
                    return;
                }else{
                    nums[0] = nums[n--];
                    nums[n] = null;
                    //向下堆化
                    sink(nums, 0, n-1);
                }
            }

            nums[n++] = num;
            //向上堆化
            swim(nums, n-1, 0);
        }


        private void swim(Integer[] nums, int start, int end){
            while(true){
                int min = start;
                if((start - 1) / 2 >= end && nums[(start - 1) / 2] > nums[start]){
                    min = (start - 1) / 2;
                }
                if(start == min) break;
                swap(nums, start, min);
                start = min;
            }
        }


        private void sink(Integer[] nums, int start, int end){
            while(true){
                int max = start;
                if(start * 2 + 1 <= end && nums[start] > nums[start * 2 + 1]){
                    max = start * 2 + 1;
                }

                if(start * 2 + 2 <= end && nums[max] > nums[start * 2 + 2]){
                    max = start * 2 + 2;
                }

                if(start == max) break;
                swap(nums, max, start);
                start = max;
            }
        }

        private void swap(Integer[] nums, int i, int y){
            int num = nums[i];
            nums[i] = nums[y];
            nums[y] = num;
        }


        public int getLength(){
            return n;
        }

        public int getNum(){
            return nums[0];
        }
    }

}
